#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2022/5/11 21:45
# @Author  : Yizheng Dai
# @Email   : 387942239@qq.com
# @File    : _46_permute.py
from copy import deepcopy


class Solution(object):

    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        use = [False] *len(nums)

        path = []
        res = []

        def dfs():
            if len(path) == len(nums):
                res.append(deepcopy(path))
                return
            for idx in range(len(nums)):
                if use[idx]:continue
                path.append(nums[idx])
                use[idx] = True
                dfs()
                path.pop()
                use[idx] = False
        dfs()
        return res

    def permute1(self, nums):
        path = []
        res = []

        def dfs(index):
            if len(path)==len(nums):
                res.append(deepcopy(path))
                return
            for i in range(index, len(nums)):
                path.append(nums[i])
                dfs(i+1)
                path.pop()
        dfs(0)
        return res




if __name__ == '__main__':
    a = Solution().permute([0, 1])
    print(a)

